Word search¶
Time: O(MxNxL); Space: O(L); medium
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example 1:
Input: board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
],
word = "ABCCED"
Output: True
Explanation:
(0,0)A->(0,1)B->(0,2)C->(1,2)C->(2,2)E->(2,1)D
Example 2:
Input: word = “SEE”
Output: True
Example 3:
Input: word = “ABCB”
Output: False
Constraints:
board and word consists only of lowercase and uppercase English letters.
1 <= len(board) <= 200
1 <= len(board[i]) <= 200
1 <= word.length <= 10^3
[2]:
class Solution1(object):
"""
Time: O(M*N*L)
Space: O(L)
"""
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
visited = [[False for j in range(len(board[0]))] for i in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
if self.existRecu(board, word, 0, i, j, visited):
return True
return False
def existRecu(self, board, word, cur, i, j, visited):
if cur == len(word):
return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j] or board[i][j] != word[cur]:
return False
visited[i][j] = True
result = self.existRecu(board, word, cur + 1, i + 1, j, visited) or \
self.existRecu(board, word, cur + 1, i - 1, j, visited) or \
self.existRecu(board, word, cur + 1, i, j + 1, visited) or \
self.existRecu(board, word, cur + 1, i, j - 1, visited)
visited[i][j] = False
return result
[3]:
s = Solution1()
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED"
assert s.exist(board, word) == True
word = "SEE"
assert s.exist(board, word) == True
word = "ABCB"
assert s.exist(board, word) == False